import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

/**
 * 给定一个不含重复数字的数组 nums ，
 * 返回其 所有可能的全排列 。
 * 你可以按任意顺序返回答案。
 * 经典
 */
public class Q46 {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        int len = nums.length;
        if(len == 0){
            return res;
        }

        //存储走过的路径
        Deque<Integer> path = new ArrayDeque<>();
//        是否访问过
        boolean[] used = new boolean[len];
//        已经走了depth步，继续走一步
        dfs(nums,len,0,path,used,res);
        return res;
    }

    // 往下走一步
    private void dfs(int[] nums,
                     int len,
                     int depth,
                     Deque<Integer> path,
                     boolean[] used,
                     List<List<Integer>> res) {
//        已经走到头了，直接记录一下返回
        if (depth == len) {
            res.add(new ArrayList<>(path));
            return;
        }

        // 继续走
        for(int i=0;i<len;i++){
            if(used[i]){
                continue;
            }
            path.add(nums[i]);
            used[i] = true;
            dfs(nums,len,depth+1,path,used,res);
            path.removeLast();
            used[i] = false;
        }
    }

    public static void main(String[] args) {
        List<List<Integer>> permute = new Q46().permute(new int[]{1, 2, 3});
        for (List<Integer> integers : permute) {
            for (Integer integer : integers) {
                System.out.print(integer);
            }
            System.out.println();
        }
    }
}
